/**************************************************************
          File Name:binary_search_tree.c
          Author: Abby Cin
          Mail: abbytsing@gmail.com
          Created Time: 2015年04月22日 22:35:40
***************************************************************/

#include<stdio.h>
#include<stdlib.h>

typedef struct node{
    int data;
    struct node *p, *left, *right;
    int key;
} Node;

typedef struct tree{
    Node *root;
} Tree;

void another_insert(Tree *T, Node *z)
{
    Node *x, *y;
    x = T->root;
    y = NULL;

    /*
     traversing tree to determine which branch to insert node x
     ended when x is the leaf of this Tree, and now y is x.p
     such that:
                x.p == y
                / \
              /    \
    x.right(NULL)   x.left(NULL)
    */
    while(x != NULL)
    {
        y = x;              /* y keeps the value of x before x point itself to its child */
        if(z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    z->p = y;            /* y is x.right.p or x.left.p or still NULL */
    if(y == NULL)       /* obviously, tree T is empty */
        T->root = z;     /* makes z be the root */
    else if(z->key < y->key)
        y->left = z;
    else
        y->right = z;
}

void build_or_insert_binary_tree(Tree *T, int A[], int size)
{
    Node *tmp;
    int i;

    for(i=0; i<size; i++)
    {
        tmp = (Node *)malloc(sizeof(Node));
        if(tmp == NULL)
        {
            fprintf(stderr, "cannot allocate space!\n");
            exit(1);
        }
        tmp->key = A[i];
        tmp->left = tmp->right = tmp->p = NULL;
        another_insert(T, tmp);
    }
}

void in_order_traversing(Node *root)
{
    if(root != NULL)
    {
        in_order_traversing(root->left);
        printf("key = \e[36m%d\e[0m\n", root->key);
        in_order_traversing(root->right);
    }
}

Node *minimum_key(Node *root)
{
    Node *tmp = root;
    while(tmp->left != NULL)
        tmp = tmp->left;
    return tmp;
}

Node *maximum_key(Node *root)
{
    Node *tmp = root;
    while(tmp->right != NULL)
        tmp = tmp->right;
    return tmp;
}

Node *tree_search_loop(Node *root, int k)
{
    Node *tmp;
    tmp = root;
    while(tmp != NULL && k != tmp->key)
    {
        if(k < tmp->key)
            tmp = tmp->left;
        else
            tmp = tmp->right;
    }
    if(tmp == NULL)
        printf(":((( not found!\n");
    else
        printf(":) found key: %d\n", tmp->key);
    return tmp;
}

Node *recurse(Node *root, int k)
{
    Node *tmp;
    tmp = root;

    if(tmp == NULL || tmp->key == k)
        return tmp;
    if(tmp->key > k)
        return recurse(tmp->left, k);
    else
        return recurse(tmp->right, k);
}

Node *tree_search_recurse(Node *root, int k)
{
    Node *tmp = NULL;

    tmp = recurse(root, k);
    if(tmp == NULL)
        printf(":((( not found!\n");
    else
        printf(":) found key: %d\n", tmp->key);
    return tmp;
}

Node *tree_successor_key(Node *node)
{
    Node *tmp = node;
    Node *y = NULL;

    if(tmp != NULL)
        return minimum_key(tmp);

    y = tmp->p;
    while(y != NULL && tmp == y->right)
    {
        tmp = y;
        y = y->p;
    }
    return y;
}

void transplant(Tree *T, Node *u, Node *v)
{
    if(u->p == NULL)                           /* u is the root */
        T->root = v;
    else if(u == u->p->left)                    /* u is the left child */
        u->p->left = v;
    else
        u->p->right = v;
    if(v != NULL)
        v->p = u->p;
}

void tree_delete(Tree *T, Node *z)
{
    Node *tmp;
    if(z->left == NULL)
        transplant(T, z, z->right);
    else if(z->right == NULL)
        transplant(T, z, z->left);
    else
    {
        tmp = tree_successor_key(z->right);
        if(tmp->p != z)
        {
            transplant(T, tmp, tmp->right);
            tmp->right = z->right;
            tmp->right->p = tmp;
        }
        transplant(T, z, tmp);
        tmp->left = z->left;
        tmp->left->p = tmp;
    }
    free(z);
}

void destroy_tree(Node *root)
{
    if(root != NULL)
    {
        if(root->left != NULL)
            destroy_tree(root->left);
        if(root->right != NULL)
            destroy_tree(root->right);
        printf("releasing \e[35m%d\e[0m\n", root->key);
        free(root);
        root = NULL;
    }
}

int main(int argc, char *argv[])
{
    Tree *T;
    Node *tmp;
    int size;
    int A[] = {1,3,9,2,1992,1989};
    size = sizeof(A) / sizeof(int);

    T = (Tree *)malloc(sizeof(Tree));       // release in destroy_tree()

    build_or_insert_binary_tree(T, A, size);
    in_order_traversing(T->root);
    tmp = minimum_key(T->root);
    printf("minimum_key is: \e[32m%d\e[0m\n", tmp->key);
    tmp = maximum_key(T->root);
    printf("maximum_key is: \e[32m%d\e[0m\n", tmp->key);
    tree_search_loop(T->root, 3);
    tree_search_recurse(T->root, 3);

    if(T->root->right)
    {
        tmp = tree_successor_key(T->root->right);
        printf("T->root->right->key = %d\t", T->root->right->key);
        printf("its successor is: %d\n", tmp->key);
    }
    printf("enter a key to delete:");
    scanf("%d", &size);
    tmp = tree_search_loop(T->root, size);
    if(tmp == NULL)
        printf("\e[43mkey not found\e[0m\n");
    else
    {
        printf("-------------after deleting \e[34m%d\e[0m----------------\n", tmp->key);
        tree_delete(T, tmp);
    }
    in_order_traversing(T->root);
    destroy_tree(T->root);
    free(T);

    return 0;
}
